package com.itheima.datastructure;

import java.util.Queue;

public class E01Leetcode206 {
    // 方法1
    public static ListNode reverseList1(ListNode head) {
        ListNode n1 = null;
        ListNode p = head;

        while(p != null){
            n1 = new ListNode(p.val,n1);
            p = p.next;
        }
        return n1;
    }

    // 方法2
//    public ListNode reverseList2(ListNode head) {
//    }

    // 方法3  - 递归

    public static ListNode reverseList3(ListNode p){
        if(p == null || p.next == null){
            return p;
        }

        ListNode last = reverseList3(p.next);

        // p = 4 p.next = 5
        p.next.next = p;
        // 最后一个元素指向null
        p.next = null;
        return last;
    }

    // 方法4
    public static ListNode reverseList4(ListNode o1){
        // 1. 空链表 2. 一个元素
        if(o1 == null || o1.next == null){
            return o1;
        }
        // 新链表
        ListNode n1 = o1;
        ListNode o2 = o1.next;
        // 将旧链表的第二个元素从旧链表中断开
        while(o2 != null){
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    // 方法5
    public static ListNode reverseList5(ListNode o1){
        // 1. 空链表 2. 一个元素
        if(o1 == null || o1.next == null){
            return o1;
        }
        // 1. 空链表 2. 一个元素
        ListNode n1 = null;
        while (o1 != null){
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1  = o2;
        }

        return n1;
    }



    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode listNode = reverseList3(listNode1);

        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }


    }
}
